# Le logiciel est compose de deux librairies Python, l'une pour les
# automates et l'autre pour les grammaire. Il faut donc programmer en
# Python pour utiliser le logiciel. Heureusement, Python est facile a
# utiliser et vous pourrez copier les exemples donnes dans ce fichier.
#
# Chaque exercice sera donc ecrit dans un fichier avec l'extension .py
# et il pourra etre execute avec la commande :
#    python mon_fichier.py
#
# Ce logiciel fonctionne sous Linux avec Python (version 2.2.3
# minimum), il est possible qu'il fonctionne sous Windows mais cela
# n'a pas ete teste...
#
# Un tutoriel Python est disponible sur http://www.python.org
# Un mini-cours de Python est donne ci-dessous.
#
# Python est sensible aux majuscules/minuscules, ainsi, le booleen
# "vrai" s'ecrit "True", avec la majuscule initiale.
#
# Les commentaires sont introduits par un "#" et s'etendent jusqu'a la
# fin de la ligne. Tout le texte que vous lisez est un long
# commentaire.
#
# Les chaines de caracteres s'ecrivent "ainsi" ou 'ainsi' (les deux
# syntaxes existent).
#
# Une liste s'ecrit entre crochets, comme dans :
#    [1, 2, 3]
# qui est une liste de trois entiers.
#
# L'affectation d'ecrit avec un simple "=", comme dans :
#    var = 1
# qui affecte 1 a la variable var. En Python, on ne declare pas les
# variables, il suffit de faire l'assignation pour creer la variable.
#
# On appelle une fonction en donnant son nom puis des parametres entre
# parentheses, s'il n'y a pas d'argument, on doit quand meme donner
# les parentheses.
#
# Python est oriente objet (comme Java ou C++), toutes les valeurs
# sont des objets et possedent des methodes ou des variables membres.
# On accede a ces champs avec un ".", par exemple,
#     lst.sort()
# appelle la methode "sort" de l'objet stocke dans la variable lst.
#
# Les erreurs donennt lieu a des exceptions, qui, si on ne fait rien,
# arretent le programme en affichant un message de diagnostique.

print("###############")  # affichage pour aider la lecture
print("## automates ##")  # lors de l'execution du programme
print("###############")  # (il affiche beaucoup de choses !)

# importation de la librairie
from .automata import *

# creation d'un automate dans la variable a
a = Automaton()

# pour ajouter un etat, on donne son numero et on indique s'il est
# initial ou final, il peut etre les deux mais on ne peut avoir qu'un
# etat initial (si on en met plusieur, le dernier ajoute sera utilise)
a.add_state(0, initial=True, final=False)
a.add_state(1, initial=False, final=True)

# pour ajouter une transition, on donne l'etat de depart, celui
# d'arrivee (qui peut etre le meme) et la lettre de la transition (un
# seul caractere pour une lettre ou une chaine vide pour epsilon)
a.add_transition(0, 0, "a")
a.add_transition(0, 1, "b")
a.add_transition(1, 0, "")

# l'automate qu'on a construit peut etre affiche avec la commande
# print qui en donne une representation textuelle
print("### affichage du premier automate")
print(a)
print()

# si le logiciel GraphViz est installe, on peut aussi creer une
# representation graphique de l'automate, dans un fichier au format
# "eps", "png" ou "jpg". L'avantage du format "eps" est qu'on peut
# zoomer et imprimer en bonne qualite.
a.draw("exemple-1", format="eps")  # cree un fichier exemple-1.eps
a.draw("exemple-1", format="png")  # cree un fichier exemple-1.png
a.draw("exemple-1", format="jpg")  # cree un fichier exemple-1.jpg

# un automate peu essayer de reconnaitre une chaine de caracteres,
# pour cela il y a deux methodes. La premiere renvoie juste un booleen
# indiquant si le mot est reconnu, la seconde renvoie une liste
# (alternant numeros d'etats et caracteres reconnus) qui correspond au
# chemin utilise pour reconnaitre la chaine (si la chaine n'est pas
# reconnue, None est renvoye).
print("### reconnaissance de chaines par l'automate")
print(a.match("abaabaaab"))  # affiche True
print(a.path("abaabaaab"))   # affiche le chemin
print(a.match("a"))  # affiche False (non reconnu)
print(a.path("a"))   # affiche None (non reconnu)

# une methode permet de determiniser un automate, elle renvoie un
# nouvel automate qu'il faut sauver dans une variable
a1 = a.determinize()
print("### affichage de l'automate deterministe")
print(a1)  # affiche le resultat, les etats sont des classes
print()

# on peut aussi demander l'affichage du deroulement de l'algorithme de
# determinisation
print("### affichage du deroulement de l'algo de determinisation")
a1 = a.determinize(verbose=True)  # meme resultat mais affiche des
                                  # messages pendant le calcul
a1.renumber().draw("exemple-1-num", format="png")
print()

# on peut aussi minimiser un automate, ici il est deja minimal, on
# verra plus tard de vraies utilisations
print("### affichage du deroulement de l'algo de minimisation")
a2 = a1.minimize()              # version silencieuse
a2 = a1.minimize(verbose=True)  # version "bavarde"
print()

# si on affiche a2, on verra que les etats sont des classes de
# classes, comme "((0, 1),)" qui contient la classe "(0, 1)" qui elle
# meme contient les etats 0 et 1 de l'automate de depart. Pour eviter
# de garder les classes, on peut renumeroter les etats d'un automate
# en les remplacant tous par des nombres. La methode "renumber"
# renvoie aussi un nouvel automate.
a3 = a1.renumber()  # il y a aussi la version bavarde avec
                    # "verbose=True"

# on pouvait aussi enchainer toutes ces commandes :
a4 = a.determinize().minimize().renumber()

print("############################")
print("## expressions regulieres ##")
print("############################")

# importation de la librairie, c'est celle des automates
from .regexps import *

# creation d'une regexp pour la chaine "abc", on la sauve dans la
# variable abc, c'est plus simple :
abc = Word("abc")
print("### affichage de la premiere regexp")
print(abc)  # affiche simplement "abc" (sans les guillements)
# lorsqu'on affiche ainsi une regexp, on voit apparraitre la syntaxe
# habituelle

# l'operateur | entre regexp a le sens habituel, par exemple :
print("### affichage de la deuxieme regexp")
print(Word("a") | Word("b") | Word("c"))  # a|b|c

# la concatenation s'ecrit avec l'operateur &
print("### affichage de la troisieme regexp")
print(Word("a") & Word("b") & Word("c"))  # abc
# Word("abc") est donc une version optimisee de l'expression
# precendente, on pourra voir la difference sur les automates

# les deux operateurs precedents utilisent la construction de
# Thompson, on peut optimiser la taille de l'automate en utilisant
# d'autres constructions :

# version optimisee de a|b|c
print("### affichage de la quatrieme regexp")
print(Any("abc"))  # [abc]  (syntaxe de Flex)

# une regexp possede une methode star pour l'etoile de Kleen (*) et
# une methode pstar pour l'etoile propre (+)
print("### affichage de la cinquieme et sixieme regexp")
print(Any("abc").star())  # [abc]*
print(Any("abc").pstar())  # [abc]+

# il existe une version optimisee pour Any("abc").star() qui ne cree
# qu'un etat, alors que la methode star utilise la construction de
# Thompson et cree plus d'etats
print("### affichage de la septieme regexp")
print(AnyStar("abc"))  # [abc]*  (avec un seul etat)

# on peut recuperer l'automate d'une regexp par le champ automaton
r = (Word("a")|Word("b")|Word("c")).star()
a = r.automaton
a.draw("exemple-2")  # => fichier exemple-2.eps

# on peut dessiner les automates des versions optimisees
r = Any("abc").star()
r.automaton.draw("exemple-3")  # plus petit
r = AnyStar("abc")
r.automaton.draw("exemple-4")  # encore plus petit

# l'automate d'une regexp peut etre determinise et minimise
r = (Word("abc").star() | Word("cba")) & Any("abc").pstar()
print("### affichage du detail de calcul de l'automate deterministe")
r1 = r.automaton.determinize(verbose=True)
print()
print("### affichage du detail de calcul de l'automate deterministe minimal")
a = r1.minimize(verbose=True).renumber()
print()
a.draw("exemple-5")  # l'automate minimal pour ((abc)*|cba)([abc]+)

# plus confortable que les constructions ci-dessus, on peut aussi
# utiliser le compilateur d'expressions regulieres qui fabrique un
# automate
a = compile("[abc]*a(ba(a*|b*))+c")

# on peut aussi demander la determinisation ou la minimisation
a = compile("[abc]*a(ba(a*|b*))+c", determinize=True)
a = compile("[abc]*a(ba(a*|b*))+c", minimize=True)

print("################")
print("## grammaires ##")
print("################")

# importation de la librairie
from .grammars import *

# definition de symboles non terminaux, on les sauve dans des
# variables
E = Symbol("E", False)
T = Symbol("T", False)
F = Symbol("F", False)

# definition de symbols terminaux
num = Symbol("num")
plus = Symbol("+")
minus = Symbol("-")
mult = Symbol("*")
div = Symbol("/")
left = Symbol("(")
right = Symbol(")")

# creation d'une grammaire vide
etf = Grammar()

# on ajoute des regles, on donne en premier le non terminal qui sera
# derive et ensuite la liste des terminaux, l'axiome de la grammaire
# sera le premier non terminal qu'on ajoute, ici E
etf.add(E, [T])               # E -> T
etf.add(E, [E, plus, T])      # E -> E + T
etf.add(E, [E, minus, T])     # E -> E - T
etf.add(T, [F])               # T -> F
etf.add(T, [T, mult, F])      # T -> T * F
etf.add(T, [T, div, F])       # T -> T / F
etf.add(F, [num])             # F -> num
etf.add(F, [left, E, right])  # F -> ( E )

# on peut afficher une grammaire
print("### affichage de la grammaire ETF")
print(etf)
print()

# on peut rendre la grammaire propre
etf1 = etf.clean()  # ici on obtiendra la meme car etf est propre
# il y aussi la version bavarde avec "verbose=True" qui detaille le
# deroulement de l'algorithme (ce qui ne change rien ici puisque la
# grammaire est propre)

# on peut supprimer la recursivite a gauche, en version bavarde on
# verra le detail de l'algorithme
etf2 = etf1.derecursify()

# on peut enfin factoriser a gauche (mais ici, il n'y a rien a faire
# de nouveau)
etf3 = etf2.factorize()

# toutes ces etapes sont automatises lorsqu'on construit la table
# LL(1), en mode bavard, on verra :
#  - le nettoyage
#  - la suppression de la recursivite
#  - la factorisation
#  - le calcul de Premier (first)
#  - le calcul de Suivant (next)
#  - la construction de la table
# Le resultat est une table LL(1) qu'on peut afficher
print("### construction (avec les details) de la table LL(1) de ETF")
table = etf.LL1(verbose=True)
print("### affichage de la table LL(1) de ETF")
print(table)  # affiche toutes les colonnes de chaque ligne
print()

# la table permet l'analyse, pour cela on doit fournir une liste de
# symboles terminaux, on peut la construire soi-meme ou utiliser la
# fonction tokenize ci-dessous. ATTENTION, cette fonction ne marche
# que pour la grammaire ETF

def tokenize (text) :
    import re
    result = []
    for token in re.findall("[0-9]+|[+/*-]|[()]", text) :
        try :
            result.append(Symbol("num", value=int(token)))
        except :
            result.append(Symbol(token))
    return result

# pour decouper une chaine en symboles terminaux d'une seule lettre,
# on peut utiliser la fonction suivante

def chars (text) :
    return [Symbol(c, final=True) for c in text]

# grace a cette fonction, on peut ecrire l'expression de facon normale
# et en demander l'analyse, avec le detail de l'execution
print("### detail de l'analyse LL(1) de ETF sur l'expression (2+3)*(4-5)")
tree = table.match(tokenize("(2+3)*(4-5)"), verbose=True)
print()

# l'arbre ainsi obtenu peut etre affiche textuellement :
print("### affichage de l'arbre de derivation de (2+3)*(4-5)")
print(repr(tree))  # si on fait juste "print tree", on ne verra pas le
print()             # detail de l'arbre, juste l'axiome, repr demande
                  # une representation detaille

# on peut aussi dessiner cet arbre, de la meme  facon qu'on peut
# dessiner un automate :
tree.draw("exemple-6")  # => fichier exemple-6.eps
tree.draw("etf-ll1", format="png")

# on remarque dans les messages des symboles comme "num:2", il s'agit
# d'une version du symbole num qui contient en plus la vraie valeur du
# nombre, ce qui aide a duivre le deroulement de l'analyse, on peut
# les fabriquer soi-meme :
print("### detail de l'analyse LL(1) de ETF sur l'expression 4+5")
table.match([Symbol("num", value=4), plus, Symbol("num", value=5)], verbose=True)
# ici, on n'a pas garde l'arbre renvoye
print()

# on peut recommencer tout ca avec SLR, comme on n'a pas vu en cours
# la construction de la tabke SLR, il n'est pas utile de la demander
# un mode bavard :
table = etf.SLR()
print("### affichage de la table SLR pour ETF")
print(table)
print()

# l'analyse est appelee de la meme facon, sauf qu'elle revoie l'arbre
# de derivation qu'on peut sauvegarder dans une variable. Si l'analyse
# echoue, None est renvoye
print("### detail de l'analyse SLR de ETF sur l'expression (2+3)*(4-5)")
tree = table.match(tokenize("(2+3)*(4-5)"), verbose=True)
print()

# l'arbre ainsi obtenu peut etre affiche textuellement :
print("### affichage de l'arbre de derivation de (2+3)*(4-5)")
print(repr(tree))  # si on fait juste "print tree", on ne verra pas le
print()             # detail de l'arbre, juste l'axiome, repr demande
                  # une representation detaille

# on peut aussi dessiner cet arbre, de la meme  facon qu'on peut
# dessiner un automate :
tree.draw("exemple-7")  # => fichier exemple-6.eps
tree.draw("etf-slr", format="png")
